Techniques for determining a path between two nodes in a network are well known in the art. Typically, the network topography is modeled as a graph, in which each network node is represented as a vertex, and each link of the network is represented as an edge. Network parameters, such as the available capacity of any given link, can then be represented by assigning corresponding attributes to each edge of the graph. With this arrangement, the graph can be analysed using any of a variety of well-known algorithms (such as Djykstra, Shortest Path First, etc.) to find one or more paths through the network between any two nodes.
For example, FIG. 1a shows a representative layer 2 mesh network 2 in which a set of nodes 4a-4h are interconnected via links 6. As shown in FIG. 1b, the topology of the network 2 can be modelled as a graph 8, in which each node 4 of the network 2 corresponds with a vertex 10 of the graph, and each link 6 of the network 2 corresponds with an edge 12 of the graph. Least cost end-to-end paths can then be computed between any two nodes 4 of the network 2, by analysing the graph 8 using known algorithms, such as Dijkstra etc. In the example of FIGS. 1a and 1b, two least cost end-to-end paths 14 have been computed between vertices A and H, 10a and 10h. Once computed, these paths 14 can be used to set up corresponding end-to end connections (not shown) through the network 2.
The above-described methods have been well developed for Layer-2 mesh networks such as the Internet, Ethernet mesh networks etc. It would be desirable to apply these same techniques to physical-layer networks, such as photonic mesh networks. However, at the physical layer, conventional path computations techniques do not always work. In particular, in a layer-2 network, finding a path through the network between two nodes automatically implies that packets can be routed between the two nodes. In a physical layer network, this does not always hold true, because physical limitations within the network may prevent successful data transmission even where there appears to be sufficient capacity in each link.
For example, consider a scenario in which it is desired to set up an end-to end connection ABEH between node A and node H and traversing nodes B and E (FIG. 1a), where each of the links A-B, B-E, and E-H has sufficient available capacity to support the connection. According to conventional path computation techniques, confirmation that there is sufficient capacity on each link individually implies that the end-to end connection can be set up by setting the appropriate routing state in each involved node. However, if the available capacity in each of links A-B and B-E is located on different wavelengths, for example, then the viability of the connection will depend on the availability of wavelength conversion capacity in node B. Furthermore, if the connection (or a part of the path) is not optically viable (e.g. due to attenuation or dispersion etc.), then the viability of the connection will also depend on the availability of signal regeneration capacity in at least one of nodes B and E. Conventional path computation techniques do not adequately address these issues.
A still further limitation of conventional path computation techniques is that they typically do not accommodate non-transitive characteristics of a physical network. In particular, in a physical optical network, the fact that a connection ABEH (for example) is valid, does not imply that the reverse connection “HEBA” is valid. Furthermore, if a valid connection can be set up on link AB and another valid connection can be set up on link BE, this does not imply that a valid connection ABE can be set up across both of these links.
Further limitations arise as a result of the physical layout of the optical network. In particular, it is common to locate various optical equipment (such as optical amplifiers, dispersion compensators, etc.) At various locations within the network. Typically, this equipment is co-located with the network nodes, but network operators will commonly not install all types of optical equipment at every node. This means, for example, that some nodes will have an optical dispersion compensator, but others will not. In this situation, it is possible, for a scenario to arise in which connection ABEH is viable, but a shorter (and thus presumably easier to implement) connection ABE is not viable, because the needed dispersion compensation is only located at node H.
In view of the above issues, it is common practice in photonic networks to use a conventional path computation technique to identify one or more candidate paths between two nodes. Each candidate path is then analysed, using a different process, to determine whether or not a viable connection can be set up along that path, given the physical topology and constraints of the network and taking into account any requirements for wavelength conversion, signal regeneration, dispersion compensation, and optical amplification, for example. A limitation of this approach is that path validation can require significant amounts of time to complete, and, if a candidate path is determined to be invalid, this step must be repeated for another candidate path. Consequently, the set-up of connections though a physical-layer photonic network tends to be time consuming and laborious for network managers.
Techniques for computing a path through a photonic network that overcome limitations of the prior art remain highly desirable.